package day_2022_9_to_12.Day;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/11/17 22:19
 **/
public class Day73_1_Num792_NumMatchingSubseq {
    class Solution {
        public int numMatchingSubseq(String s, String[] words) {
            List<Integer> pos[]=new List[26];
            char c[]=s.toCharArray();
            for(int i=0;i<26;i++){
                pos[i]=new ArrayList<>();
                pos[i].add(-1);
            }
            for(int i=0;i<c.length;i++){pos[c[i]-'a'].add(i);}
            int ans=words.length;
            for(int i=0;i<words.length;i++){
                int pre=-1;
                for(char ch:words[i].toCharArray()){
                    int next=nextPos(pos,pre,ch-'a');
                    if(next==-1){
                        ans--;
                        break;
                    }
                    pre=next;
                }
            }
            return ans;
        }
        int nextPos(List<Integer> pos[],int idx,int ch){
            if(pos[ch].get(pos[ch].size()-1)<=idx){return -1;}
            int l=0,r=pos[ch].size()-1;
            while(l<r){
                int mid=(l+r)>>1;
                if(pos[ch].get(mid)>idx){r=mid;}
                else{l=mid+1;}
                if(l==r-1){
                    if(pos[ch].get(l)>idx){r=l;}
                    break;
                }
            }
            return pos[ch].get(r);
        }
    }
}